/**
 * //给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
 * //
 * // k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 * //
 * // 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 * //
 * //
 * //
 * // 示例 1：
 * //
 * //
 * //输入：head = [1,2,3,4,5], k = 2
 * //输出：[2,1,4,3,5]
 * //
 * //
 * // 示例 2：
 * //
 * //
 * //
 * //
 * //输入：head = [1,2,3,4,5], k = 3
 * //输出：[3,2,1,4,5]
 * //
 * //
 * //
 * //提示：
 * //
 * //
 * // 链表中的节点数目为 n
 * // 1 <= k <= n <= 5000
 * // 0 <= Node.val <= 1000
 * //
 * //
 * //
 * //
 * // 进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？
 * //
 * //
 * //
 * //
 * // Related Topics 递归 链表 👍 1824 👎 0
 */

package com.xixi.dataStructure.lineList;

public class ID00025ReverseNodesInKGroup {
    public static void main(String[] args) {

        Solution solution = new ID00025ReverseNodesInKGroup().new Solution();

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        node1.next = node2;

        System.out.println(solution.reverseKGroup(node1, 2));
    }


//leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode kLastTail; //initial sentry node as kLastTail, move when every k group has been reversed
        public ListNode kTail;

        public ListNode reverseKGroup(ListNode head, int k) {

            if (k == 1) return head;

            ListNode resHead = new ListNode();
            resHead.next = head; //sentry node;

            //reverseK

            kLastTail = resHead; //initial sentry node as kLastTail
            kTail = head;
            while (kLastTail != null) {
                kLastTail = recursiveDiveK(kTail, k, 1); //kLastTail move when every k group has been reversed
                if (kLastTail == null) break;
                kTail = kTail.next; //kTail now is pointing to next groups head(before reverse), that head will be the next kTail;
            }


            return resHead.next;


        }


        //kNow : move this pin to find last k node
        public ListNode recursiveDiveK(ListNode kNow, int k, int index) {

            if (kNow == null) { //this group node have enough k node, and already reach to the end;
                return null;
            }

            if (index == k) { //found real kHead
                kLastTail.next = kNow; //lastTail point to this group's head;
                kTail.next = kNow.next; //this Tail point to next group's head;
                return kNow;
            }

            ListNode kNext = recursiveDiveK(kNow.next, k, index + 1);

            if (kNext == null) return null; // if not enough k, return null,and not reverse k group;

            //Next Node point to this node
            kNext.next = kNow;
            return kNow;
        }


    }
//leetcode submit region end(Prohibit modification and deletion)


}